﻿// Copyright (c) Ryan Schmidt (rms@gradientspace.com) - All Rights Reserved
// Distributed under the Boost Software License, Version 1.0. http://www.boost.org/LICENSE_1_0.txt
using System;
using System.Collections.Generic;
using System.Threading;
using g3;

namespace gs
{
	/// <summary>
	/// This class sorts a set of mesh components.
	/// </summary>
	public class MeshSpatialSort
	{
		// ComponentMesh is a wrapper around input meshes
		public List<ComponentMesh> Components;

		// a MeshSolid is an "Outer" mesh and a set of "Cavity" meshes 
		// (the cavity list includes contained open meshes, though)
		public List<MeshSolid> Solids;

		public bool AllowOpenContainers = false;
		public double FastWindingIso = 0.5f;


		public MeshSpatialSort()
		{
			Components = new List<ComponentMesh>();
		}


		public void AddMesh(DMesh3 mesh, object identifier, DMeshAABBTree3 spatial = null)
		{
			var comp = new ComponentMesh(mesh, identifier, spatial);
			if (spatial == null)
			{
				if (comp.IsClosed || AllowOpenContainers)
				{
					comp.Spatial = new DMeshAABBTree3(mesh, true);
				}
			}

			Components.Add(comp);
		}




		public class ComponentMesh
		{
			public object Identifier;
			public DMesh3 Mesh;
			public bool IsClosed;
			public DMeshAABBTree3 Spatial;
			public AxisAlignedBox3d Bounds;

			// meshes that contain this one
			public List<ComponentMesh> InsideOf = new List<ComponentMesh>();

			// meshes that are inside of this one
			public List<ComponentMesh> InsideSet = new List<ComponentMesh>();

			public ComponentMesh(DMesh3 mesh, object identifier, DMeshAABBTree3 spatial)
			{
				this.Mesh = mesh;
				this.Identifier = identifier;
				this.IsClosed = mesh.IsClosed();
				this.Spatial = spatial;
				Bounds = mesh.CachedBounds;
			}

			public bool Contains(ComponentMesh mesh2, double fIso = 0.5f)
			{
				if (this.Spatial == null)
				{
					return false;
				}
				// make sure FWN is available
				this.Spatial.FastWindingNumber(Vector3d.Zero);

				// block-parallel iteration provides a reasonable speedup
				int NV = mesh2.Mesh.VertexCount;
				bool contained = true;
				gParallel.BlockStartEnd(0, NV - 1, (a, b) =>
				{
					if (contained == false)
					{
						return;
					}

					for (int vi = a; vi <= b && contained; vi++)
					{
						Vector3d v = mesh2.Mesh.GetVertex(vi);
						if (Math.Abs(Spatial.FastWindingNumber(v)) < fIso)
						{
							contained = false;
							break;
						}
					}
				}, 100);

				return contained;
			}
		}



		public class MeshSolid
		{
			public ComponentMesh Outer;
			public List<ComponentMesh> Cavities = new List<ComponentMesh>();
		}







		public void Sort()
		{
			int N = Components.Count;

			ComponentMesh[] comps = Components.ToArray();

			// sort by bbox containment to speed up testing (does it??)
			Array.Sort(comps, (i, j) =>
			{
				return i.Bounds.Contains(j.Bounds) ? -1 : 1;
			});

			// containment sets
			bool[] bIsContained = new bool[N];
			var ContainSets = new Dictionary<int, List<int>>();
			var ContainedParents = new Dictionary<int, List<int>>();
			var dataLock = new SpinLock();

			// [TODO] this is 90% of compute time...
			//   - if I know X contains Y, and Y contains Z, then I don't have to check that X contains Z
			//   - can we exploit this somehow?
			//   - if j contains i, then it cannot be that i contains j. But we are
			//     not checking for this!  (although maybe bbox check still early-outs it?)

			// construct containment sets
			gParallel.ForEach(Interval1i.Range(N), (i) =>
			{
				ComponentMesh compi = comps[i];

				if (compi.IsClosed == false && AllowOpenContainers == false)
				{
					return;
				}

				for (int j = 0; j < N; ++j)
				{
					if (i == j)
					{
						continue;
					}

					ComponentMesh compj = comps[j];

					// cannot be contained if bounds are not contained
					if (compi.Bounds.Contains(compj.Bounds) == false)
					{
						continue;
					}

					// any other early-outs??
					if (compi.Contains(compj))
					{

						bool entered = false;
						dataLock.Enter(ref entered);

						compj.InsideOf.Add(compi);
						compi.InsideSet.Add(compj);

						if (ContainSets.ContainsKey(i) == false)
						{
							ContainSets.Add(i, new List<int>());
						}

						ContainSets[i].Add(j);
						bIsContained[j] = true;
						if (ContainedParents.ContainsKey(j) == false)
						{
							ContainedParents.Add(j, new List<int>());
						}

						ContainedParents[j].Add(i);

						dataLock.Exit();
					}

				}
			});


			var solids = new List<MeshSolid>();
			var used = new HashSet<ComponentMesh>();

			var CompToOuterIndex = new Dictionary<ComponentMesh, int>();

			var ParentsToProcess = new List<int>();


			// The following is a lot of code but it is very similar, just not clear how
			// to refactor out the common functionality
			//   1) we find all the top-level uncontained polys and add them to the final polys list
			//   2a) for any poly contained in those parent-polys, that is not also contained in anything else,
			//       add as hole to that poly
			//   2b) remove all those used parents & holes from consideration
			//   2c) now find all the "new" top-level polys
			//   3) repeat 2a-c until done all polys
			//   4) any remaining polys must be interior solids w/ no holes
			//          **or** weird leftovers like intersecting polys...

			// add all top-level uncontained polys
			for (int i = 0; i < N; ++i)
			{
				ComponentMesh compi = comps[i];
				if (bIsContained[i])
				{
					continue;
				}

				var g = new MeshSolid() { Outer = compi };

				int idx = solids.Count;
				CompToOuterIndex[compi] = idx;
				used.Add(compi);

				if (ContainSets.ContainsKey(i))
				{
					ParentsToProcess.Add(i);
				}

				solids.Add(g);
			}


			// keep iterating until we processed all parents
			while (ParentsToProcess.Count > 0)
			{
				var ContainersToRemove = new List<int>();

				// now for all top-level components that contain children, add those children
				// as long as they do not have multiple contain-parents
				foreach (int i in ParentsToProcess)
				{
					ComponentMesh parentComp = comps[i];
					int outer_idx = CompToOuterIndex[parentComp];

					List<int> children = ContainSets[i];
					foreach (int childj in children)
					{
						ComponentMesh childComp = comps[childj];
						Util.gDevAssert(used.Contains(childComp) == false);

						// skip multiply-contained children
						List<int> parents = ContainedParents[childj];
						if (parents.Count > 1)
						{
							continue;
						}

						solids[outer_idx].Cavities.Add(childComp);

						used.Add(childComp);
						if (ContainSets.ContainsKey(childj))
						{
							ContainersToRemove.Add(childj);
						}
					}
					ContainersToRemove.Add(i);
				}

				// remove all containers that are no longer valid
				foreach (int ci in ContainersToRemove)
				{
					ContainSets.Remove(ci);

					// have to remove from each ContainedParents list
					var keys = new List<int>(ContainedParents.Keys);
					foreach (int j in keys)
					{
						if (ContainedParents[j].Contains(ci))
						{
							ContainedParents[j].Remove(ci);
						}
					}
				}

				ParentsToProcess.Clear();

				// ok now find next-level uncontained parents...
				for (int i = 0; i < N; ++i)
				{
					ComponentMesh compi = comps[i];
					if (used.Contains(compi))
					{
						continue;
					}

					if (ContainSets.ContainsKey(i) == false)
					{
						continue;
					}

					List<int> parents = ContainedParents[i];
					if (parents.Count > 0)
					{
						continue;
					}

					var g = new MeshSolid() { Outer = compi };

					int idx = solids.Count;
					CompToOuterIndex[compi] = idx;
					used.Add(compi);

					if (ContainSets.ContainsKey(i))
					{
						ParentsToProcess.Add(i);
					}

					solids.Add(g);
				}
			}


			// any remaining components must be top-level
			for (int i = 0; i < N; ++i)
			{
				ComponentMesh compi = comps[i];
				if (used.Contains(compi))
				{
					continue;
				}

				var g = new MeshSolid() { Outer = compi };
				solids.Add(g);
			}

			Solids = solids;
		}


	}
}
